#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

//珠宝的最高价值，不同路径问题的一种变式
//变化在于dp表中表示的是路径里分别累加的和，而不是路径了
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        //创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //初始化
        dp[1][1] = frame[0][0];
        //填表
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        //返回值
        return dp[m][n];
    }
};


int main()
{

	return 0;
}


